package com.threadedbinarytree;

import com.threadedbinarytree.HeroNode;

/**
 * 实现线索化功能的BinaryTree
 */
public class ThreadedBinaryTree {
    private HeroNode root;
    //在递归线索化时，辅助变量用于保存当前的结点的前驱结点
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }



    /**
     * 二叉树中序线索化方法
     *
     * @param node 表示当前需要线索化的结点
     */
    public void threadedNodes(HeroNode node) {
        //结点不能为空
        if (node == null) {
            return;
        }
        //线索化左子树
        threadedNodes(node.getLeft());
        //线索化当前节点,结束左子树递归时，表示当前结点已经没有了左子结点，则让当前结点left指向前驱结点pre
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        //处理后继结点,即让递归结束后返回上一个递归时
        //让pre(上一个递归，需要设置后继结点的结点)指向当前结点
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //保留上一次递归时的结点
        pre = node;

        //线索化右子树
        threadedNodes(node.getRight());
    }
    /**
     * 重载线索话方法，直接传入root
     */
    public void threadedNodes() {
        this.threadedNodes(root);
    }

    /**
     * 中序线索化二叉树的遍历
     * 线索化二叉树后，由于结点的空指针指向了该节点的前后驱结点，所以不能使用普通二叉树时的递归遍历方法，会出现死循环
     * 通过结点类型来进行判断
     */
    public void threadedList(){
        //辅助变量保存当前结点。用于遍历二叉树
        HeroNode node = root;
        //中序遍历的最后一个结点的后继结点一定为null，所以只要node!=null就一直遍历
        while(node != null){
            //中序遍历进行"左递归"输出
            while(node.getLeftType() == 0){
                node = node.getLeft();
            }
            System.out.println(node);
            //中序遍历的下一位数也就是结点的后继结点，即输出后继结点
            //如果该结点的右指针一直是后继结点就一直输出
            while(node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            //否则，该右指针为右子树，替换该结点
            node = node.getRight();
        }
    }


}
